package main

var result []string

func letterCombinations(digits string) []string {
	result = make([]string, 0)
	backtrack([]byte(digits), []byte{})
	return result
}

var m = map[byte][]byte{
	'2': {'a', 'b', 'c'},
	'3': {'d', 'e', 'f'},
	'4': {'g', 'h', 'i'},
	'5': {'j', 'k', 'l'},
	'6': {'m', 'n', 'o'},
	'7': {'p', 'q', 'r', 's'},
	'8': {'t', 'u', 'v'},
	'9': {'w', 'x', 'y', 'z'},
}

func backtrack(digits []byte, ans []byte) {
	if len(ans) == len(digits) {
		if len(ans) > 0 {
			result = append(result, string(ans))
		}
	} else {
		chars := m[digits[len(ans)]]
		for _, b := range chars {
			ans = append(ans, b)
			backtrack(digits, ans)
			ans = ans[:len(ans)-1]
		}
	}
}

func main() {
	res := letterCombinations("")
	println(res)
}
